// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// Package gcprog为压缩GC指针位图实现了一个编码器，
// 称为GC程序。
// 
// 程序格式
// 
// GC程序对一个由0和1位组成的序列进行编码，表示对象中的标量或指针字。
// 该编码是一个简单的Lempel-Ziv程序，代码可以发出文字位，并重复
// 最后n位c次。
// 
// 可能的代码是：
// 
// 00000000:停止
// 0nnnnn:从下一个（n+7）/8字节中复制n位，最低有效位第一个
// 10000000 n c:重复前n位c次；n、 c是变量
// 1nnnnnnnnn c：重复前面的n位c次；c是一个变量
// 
// 当数字n和c跟在一个代码后面时，它们被编码为变量
// 使用与encoding/binary的Uvarint相同的编码。
// 
package gcprog

import (
	"fmt"
	"io"
)

const progMaxLiteral = 127 // 文本n位代码的最大n数

// Writer是GC程序的编码器。
// 
// Writer的典型用法是调用Init，可能调用Debug，
// 进行一系列的Ptr、Advance、Repeat和Append调用
// 来描述数据类型，最后调用End。
type Writer struct {
	writeByte func(byte)
	index     int64
	b         [progMaxLiteral]byte
	nb        int
	debug     io.Writer
	debugBuf  []byte
}

// Init通过为程序中的每个字节调用writeByte来初始化w以编写新的GC程序
// 。
func (w *Writer) Init(writeByte func(byte)) {
	w.writeByte = writeByte
}

// Debug使编写器在将来调用Ptr、Advance和End等方法时打印调试跟踪以输出
// 。
// 它还可以在编码过程中启用调试检查。
func (w *Writer) Debug(out io.Writer) {
	w.debug = out
}

// BitIndex返回到目前为止写入位流的位数。
func (w *Writer) BitIndex() int64 {
	return w.index
}

// 字节将字节x写入输出。
func (w *Writer) byte(x byte) {
	if w.debug != nil {
		w.debugBuf = append(w.debugBuf, x)
	}
	w.writeByte(x)
}

// 结束标记程序的结束，写入剩余字节。
func (w *Writer) End() {
	w.flushlit()
	w.byte(0)
	if w.debug != nil {
		index := progbits(w.debugBuf)
		if index != w.index {
			println("gcprog: End wrote program for", index, "bits, but current index is", w.index)
			panic("gcprog: out of sync")
		}
	}
}

// Ptr在给定的位索引处向位流发射1。
// 也就是说，它记录了对象内存中索引的第四个字是指针。
// 当前索引和新索引之间的任何位
// 都设置为零，这意味着相应的字是标量。
func (w *Writer) Ptr(index int64) {
	if index < w.index {
		println("gcprog: Ptr at index", index, "but current index is", w.index)
		panic("gcprog: invalid Ptr index")
	}
	w.ZeroUntil(index)
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: ptr at %d\n", index)
	}
	w.lit(1)
}

// ShouldRepeat报告是否值得使用
// 使用一个Repeat来描述每个n位的c元素，
// 与只发送n位描述的c个副本相比。
func (w *Writer) ShouldRepeat(n, c int64) bool {
	// 我们是否应该直接排列位，而不是将位编码为重复？当然，如果count==1，
	// 因为没有什么可重复的，但是如果类型的普通指针位的总
	// 大小将适合
	// 4或更少字节，因为使用重复将需要
	// 刷新当前位加上
	// 重复大小和一个用于重复计数。
	return c > 1 && c*n > 4*8
}

// Repeat发出一条指令，将前n个单词的描述
// 重复c次（包括初始描述，总共c+1次）。
func (w *Writer) Repeat(n, c int64) {
	if n == 0 || c == 0 {
		return
	}
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: repeat %d × %d\n", n, c)
	}
	if n < 128 {
		w.byte(0x80 | byte(n))
	} else {
		w.byte(0x80)
		w.varint(n)
	}
	w.varint(c)
	w.index += n * c
}

// ZeroTill将零添加到位流中，直到达到给定的索引；
// 也就是说，它记录了从最近的指针到索引的第四个单词的单词是标量。
// zerotuntil通常被调用以准备重复、追加或结束调用。
func (w *Writer) ZeroUntil(index int64) {
	if index < w.index {
		println("gcprog: Advance", index, "but index is", w.index)
		panic("gcprog: invalid Advance index")
	}
	skip := (index - w.index)
	if skip == 0 {
		return
	}
	if skip < 4*8 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, "gcprog: advance to %d by literals\n", index)
		}
		for i := int64(0); i < skip; i++ {
			w.lit(0)
		}
		return
	}

	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: advance to %d by repeat\n", index)
	}
	w.lit(0)
	w.flushlit()
	w.Repeat(1, skip-1)
}

// Append将给定的GC程序发送到当前输出中。
// 调用者断言程序发出n位（描述n个字），如果不是这样，则追加panics。
func (w *Writer) Append(prog []byte, n int64) {
	w.flushlit()
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: append prog for %d ptrs\n", n)
		fmt.Fprintf(w.debug, "\t")
	}
	n1 := progbits(prog)
	if n1 != n {
		panic("gcprog: wrong bit count in append")
	}
	// 程序的最后一个字节终止程序。
	// 不要发射，否则我们自己的程序就会结束。
	for i, x := range prog[:len(prog)-1] {
		if w.debug != nil {
			if i > 0 {
				fmt.Fprintf(w.debug, " ")
			}
			fmt.Fprintf(w.debug, "%02x", x)
		}
		w.byte(x)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.index += n
}

// progbits返回程序p编码的位流长度。
func progbits(p []byte) int64 {
	var n int64
	for len(p) > 0 {
		x := p[0]
		p = p[1:]
		if x == 0 {
			break
		}
		if x&0x80 == 0 {
			count := x &^ 0x80
			n += int64(count)
			p = p[(count+7)/8:]
			continue
		}
		nbit := int64(x &^ 0x80)
		if nbit == 0 {
			nbit, p = readvarint(p)
		}
		var count int64
		count, p = readvarint(p)
		n += nbit * count
	}
	if len(p) > 0 {
		println("gcprog: found end instruction after", n, "ptrs, with", len(p), "bytes remaining")
		panic("gcprog: extra data at end of program")
	}
	return n
}

// readvarint从p读取变量，返回值和p的其余部分。
func readvarint(p []byte) (int64, []byte) {
	var v int64
	var nb uint
	for {
		c := p[0]
		p = p[1:]
		v |= int64(c&^0x80) << nb
		nb += 7
		if c&0x80 == 0 {
			break
		}
	}
	return v, p
}

// lit向w添加一个文字位。
func (w *Writer) lit(x byte) {
	if w.nb == progMaxLiteral {
		w.flushlit()
	}
	w.b[w.nb] = x
	w.nb++
	w.index++
}

// varint发出x的varint编码。
func (w *Writer) varint(x int64) {
	if x < 0 {
		panic("gcprog: negative varint")
	}
	for x >= 0x80 {
		w.byte(byte(0x80 | x))
		x >>= 7
	}
	w.byte(byte(x))
}

// flushlit刷新任何挂起的文字位。
func (w *Writer) flushlit() {
	if w.nb == 0 {
		return
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "gcprog: flush %d literals\n", w.nb)
		fmt.Fprintf(w.debug, "\t%v\n", w.b[:w.nb])
		fmt.Fprintf(w.debug, "\t%02x", byte(w.nb))
	}
	w.byte(byte(w.nb))
	var bits uint8
	for i := 0; i < w.nb; i++ {
		bits |= w.b[i] << uint(i%8)
		if (i+1)%8 == 0 {
			if w.debug != nil {
				fmt.Fprintf(w.debug, " %02x", bits)
			}
			w.byte(bits)
			bits = 0
		}
	}
	if w.nb%8 != 0 {
		if w.debug != nil {
			fmt.Fprintf(w.debug, " %02x", bits)
		}
		w.byte(bits)
	}
	if w.debug != nil {
		fmt.Fprintf(w.debug, "\n")
	}
	w.nb = 0
}
